//
// Created by Administrator on 2022/1/4.
//

#ifndef CPP_LEARNING_B_TREE_HPP
#define CPP_LEARNING_B_TREE_HPP

#include "btnode.hpp"
#include "utils.h"
#include <vector>
#include <math.h>
template <typename T>
class BTree{
protected:
    int _size; int _order; BTNodePosi(T) _root;   //关键吗的总数

    BTNodePosi(T) _hot;   // search()最后访问的非空节点位置

    void solveOverflow(BTNodePosi(T));      //插入上溢出分裂
    void solveUnderflow(BTNodePosi(T));    //插入下溢出分裂

public:
    BTree(int order){
        _order = order;
        _size = 0;
        _root = NULL;
    }
    BTNodePosi(T) search(const T&e);
    bool insert(const T&e);
    bool remove(const T&e);

};

/**
 *         0     1     2     3
 *      0     1     2     3     4
 */

// _hot 指向最后被访问节点(有可能是NULL)的父亲
template <typename T>
BTNodePosi(T) BTree<T>::search(const T&e){
    BTNodePosi(T) v = this->_root;
    _hot = NULL;
    while (v){
        int r = v->search(e);
        if((r>=0) && e == v->key[r]){
            return v;
        }else{
            _hot = v;
            v = v->child[r+1];
        }
    }
    return NULL;
}
/**
 *         0     1     2     3
 *      0     1     2     3     4
 *
 *         0     1   1.5  2     3
 *      0     1     2     3     4
 */

template <typename T>
bool BTree<T>::insert(const T&e){
    BTNodePosi(T) v = search(e);
    if(v != NULL)  return false;

    // _hot 的所有孩子必定是null;
    if(_hot == NULL){
        _hot = _root = new BTNode<T>();
    }
    int r = _hot->search(e);
    _hot->key_insert(e, r+1);
    _hot->child_insert(NULL, r+2);
    _size ++;

    solveOverflow(_hot);
    return true;

}

/**
 *          1 2 3 4 5
 *
 *                3
 *          1  2     4  5
 */
template <typename T>
void BTree<T>::solveOverflow(BTNodePosi(T) node){  //插入上溢出分裂
    while (node){
        // 发生了上溢出
        if((node->key).size() > _order-1){
            BTNodePosi(T) parent = node->parent;

            int r = int(_order / 2);

            // 分裂成两个节点
            BTNode<T>* newBtNode = new BTNode<T>;
            for(int i = (node->key).size()-1; i > r; i--){
                T ne = node->key.back();
                node->key.pop_back();
                newBtNode->key_insert(ne ,0);
            }
            newBtNode->child.clear();
            for(int i = (node->child).size()-1; i > r; i--){
                BTNodePosi(T) pe = node->child.back();
                node->child.pop_back();
                newBtNode->child_insert(pe,0);
            }

            T e = node->key.back();
            node->key.pop_back();

            if(parent == NULL){
                BTNode<T>* newParent = new BTNode<T>;
                newParent->child.clear();
                newParent->child.push_back(node);
                node->parent = newParent;
                _root = newParent;
                parent = newParent;
            }

            // 向parent节点里面插入

            int insert_index = parent->search(e);
            parent->key_insert(e,insert_index + 1);
            parent->child_insert(newBtNode,insert_index + 2);
            newBtNode->parent = parent;

            node = parent;
        }else{
            break;
        }
    }
}

template <typename T>
bool BTree<T>::remove(const T&e){
    BTNodePosi(T) v = search(e);
    if(v == NULL)  return false;       // 找不到e, 则直接失败

    // 要删除节点V里面的e, 并不是直接删除， 而是找到e的直接后继， 交换两者
    //
    int r = v->search(e);

    // B 树里面的后继
    // e的右子树里面的最左一个
    BTNodePosi(T) succ = v;
    BTNodePosi(T) succ_child = v->child[r+1];
    int succ_r = r;
    while(succ_child){
        succ = succ_child;
        succ_child = succ->child[0];  // 最左一个
        succ_r = 0;
    }

    //如果真的在e的右子树里面有后继节点
    // e的后继节点肯定没有左子树了
    if(v != succ){
        myswap(v->key[r], succ->key[succ_r]);
        succ->key_erase(0);
        succ->child_erase(0);
        _size --;
    }

    //如果e没有右子树
    // 那么直接把e删除，也把其对应的右子树（NULL） 删除
    else if(succ == v){
        succ->key_erase(r);
        succ->child_erase(r+1);
        _size --;
    }

    // 实际被删除的btnode的size会减少，要进行下溢处理
    solveUnderflow(succ);

}
// 处理下溢出
template <typename T>
void BTree<T>::solveUnderflow(BTNodePosi(T) node){
    if(node && (node->key.size() >= int((_order+1)/2)-1)) return;

    BTNodePosi(T) parent = node->parent;
    // 根节点没有数量的限制,
    // 但是如果根节点的size==0， 则没有存在的必要了
    if(parent == NULL){
        if(node->key.size()==0){
            _root = node->child[0];
            _root ->parent = NULL;
            node->child[0] = NULL;
            delete node;
        }
        return;
    }


    // 向左兄弟借一个
    // 1 先找到 node 在父节点的index， 通过指针找
    int r = parent->find(node);
    BTNodePosi(T) lbrother = NULL;
    BTNodePosi(T) rbrother = NULL;
    if((r-1)>=0){
        lbrother = parent->child[r-1];
        // 左兄弟有足够的节点
        if(lbrother->key.size() >= int((_order+1)/2)){
            //myswap(lbrother->key.back(), parent->child[r-1]);

            T x = lbrother->key.back();
            lbrother->key.pop_back();
            T py = parent->key[r-1];
            parent->key[r-1] = x;


            node->key_insert(py,0);

            BTNodePosi(T) xl = lbrother->child.back();
            lbrother->child.pop_back();
            node->child_insert(xl,0);

            //旋转之后， 不需要其他的改变， 可以终止了
            return;
        }
    }

    // 左兄第没有或者数量不够
    // 向右兄弟借一个
    if((r+1)< parent->child.size()){
        rbrother = parent->child[r+1];
        // 左兄弟有足够的节点
        if(rbrother->key.size() >= int((_order+1)/2)){
            //myswap(rbrother->key.front(), parent->child[r]);

            T x = rbrother->key.front();
            rbrother->key_erase(0);
            T py =  parent->key[r];
            parent->key[r] = x;

            node->key.push_back(py);

            BTNodePosi(T) xl = rbrother->child.front();
            rbrother->child_erase(0);
            node->child.push_back(xl);

            //旋转之后， 不需要其他的改变， 可以终止了
            return;
        }
    }


    // 如果无法发生旋转, 则只能合并
    // 和 左子树合并

    T pe = parent->key[r-1];
    if(lbrother &&   (lbrother->key.size() == int((_order+1)/2)-1) ){
        lbrother->key.push_back(pe);
        // 把node里面的全部移动到lbrother里面
        for(int i=0;i<node->key.size();i++){
            lbrother->key.push_back(node->key[i]);
        }

        for(int i=0;i<node->child.size();i++){
            lbrother->child.push_back(node->child[i]);
        }

        parent->key_erase(r-1);
        parent->child_erase(r);
        delete node;
        solveUnderflow(parent);
    }else{
        // 合并右子树
        // 把lbrother里面的全部移动到node里面

        node->key.push_back(pe);
        // 把node里面的全部移动到lbrother里面
        for(int i=0;i<rbrother->key.size();i++){
            node->key.push_back(rbrother->key[i]);
        }

        for(int i=0;i<rbrother->child.size();i++){
            node->child.push_back(rbrother->child[i]);
        }

        parent->key_erase(r);
        parent->child_erase(r+1);
        delete rbrother;
        solveUnderflow(parent);
    }

}

#endif //CPP_LEARNING_B_TREE_HPP
